package cn.xkai.exercise.a;

/**
 * @description: 数组拆分 I
 * 自己的思路：手撸快速排序，然后取偶数索引对应的数值和（Arrays.sort底层实现就是快速排序）
 * 借鉴的思路：同理
 * @author: kaixiang
 * @date: 2022/6/26
 **/
public class Solution13 {
    public int arrayPairSum(int[] nums) {
//        Arrays.sort(nums);
        quicksort(nums, 0, nums.length - 1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                sum += nums[i];
            }
        }
        return sum;
    }

    /**
     * 递归
     * @param nums
     * @param startIndex
     * @param endIndex
     */
    private void quicksort(int[] nums, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int pivot = partition(nums, startIndex, endIndex);
        quicksort(nums, startIndex, pivot - 1);
        quicksort(nums, pivot + 1, endIndex);
    }

    /**
     * 找基准点，并交换
     * @param nums
     * @param startIndex
     * @param endIndex
     * @return
     */
    private int partition(int[] nums, int startIndex, int endIndex) {
        int pivot = nums[startIndex];
        int left = startIndex;
        int right = endIndex;
        while (left != right) {
            while (left < right && nums[right] > pivot) {
                right--;
            }
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            if (left < right) {
                nums[left] = nums[left] ^ nums[right];
                nums[right] = nums[left] ^ nums[right];
                nums[left] = nums[left] ^ nums[right];
            }
        }
        nums[startIndex] = nums[left];
        nums[left] = pivot;
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {6, 2, 6, 5, 1, 2};
        Solution13 solution13 = new Solution13();
        System.out.println(solution13.arrayPairSum(nums));
    }
}
